#include "common.h"

void Sort(vector<int>& nums, int start, int end)
{
	if (start >= end) return;
	int mid = start + (end - start) / 2;
	Sort(nums, start, mid);
	Sort(nums, mid + 1, end);
	vector<int> num(end - start + 1);
	int i = start;
	int j = mid + 1;
	int k = 0;
	while (i <= mid && j <= end)
	{
		if (nums[i] <= nums[j])
		{
			num[k++] = nums[i++];
		}
		else
		{
			num[k++] = nums[j++];
		}
	}
	while (i <= mid) num[k++] = nums[i++];
	while (j <= end) num[k++] = nums[j++];
	int p = 0;
	while (p < k)
	{
		nums[p + start] = num[p];
		p++;
	}
}
vector<int> sortArray(vector<int>& nums)
{
	Sort(nums, 0, nums.size() - 1);
	return nums;
}